package primary.code08;

import lombok.extern.slf4j.Slf4j;
import primary.util.ArrayUtils;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 问题：岛屿数量
 * <p>
 * 一个矩阵中只有0（水）和1（陆地）两种值，每个陆地只能与上、下、左、右方向上的陆地相联
 * 如果有一片陆地相联，则这一片陆地被称为一座岛屿。
 * 请问：给定的矩阵中，有多少个岛屿？
 * <p>
 * 分析三
 * 优秀的广度遍历实现方式
 */
@Slf4j
public class Code02_NumIslands_3 {
    public static int numIslands(int[][] arr) {
        int num = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                if (arr[i][j] == 1) {
                    floodFill(arr, i, j);
                    num++;
                }
            }
        }
        return num;
    }

    private static void floodFill(int[][] arr, int i, int j) {
        log.info("flood fill, i: {}, j: {}", i, j);
        Queue<Integer> neighbors = new LinkedList<>();
        int nr = arr.length;
        int nc = arr[0].length;
        arr[i][j] = 0; // 进neighbors之前修改值，避免了重复进neighbors
        neighbors.add(i * nc + j); // 用一个int值表示（行+列）
        while (!neighbors.isEmpty()) {
            int cur = neighbors.poll();
            int r = cur / nc;
            int c = cur % nc;
            if (r - 1 >= 0 && arr[r - 1][c] == 1) {
                arr[r - 1][c] = 0; // 进neighbors之前修改值，避免了重复进neighbors
                neighbors.add((r - 1) * nc + c);
            }
            if (r + 1 < nr && arr[r + 1][c] == 1) {
                arr[r + 1][c] = 0;
                neighbors.add((r + 1) * nc + c);
            }
            if (c - 1 >= 0 && arr[r][c - 1] == 1) {
                arr[r][c - 1] = 0;
                neighbors.add(r * nc + c - 1);
            }
            if (c + 1 < nc && arr[r][c + 1] == 1) {
                arr[r][c + 1] = 0;
                neighbors.add(r * nc + c + 1);
            }
        }
    }

    public static void main(String[] args) {
        int[][] arr = {
                {0, 1, 1, 0, 0},
                {0, 1, 0, 0, 0},
                {0, 1, 1, 1, 0},
                {0, 0, 0, 0, 1},
                {1, 1, 0, 0, 1}
        };
        ArrayUtils.print(arr);
        int num = numIslands(arr);
        log.info("num is {}", num);
        ArrayUtils.print(arr);
    }
}
